import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * @author Wang Chen Peng
 * @date 2019/01/10
 * describe:只出现一次的数字
 * https://leetcode-cn.com/explore/featured/card/top-interview-questions-easy/1/array/25/
 */
public class SingleNumber {

    public static void main(String[] args) {
        int[] num = new int[]{4, 1, 2, 3, 2, 1,3};
        System.out.println(singleNumber1(num));
    }

    public static int singleNumber(int[] nums) {

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.remove(nums[i]);
                continue;
            }
            map.put(nums[i], nums[i]);
        }
        return (int) map.values().toArray()[0];

    }


    /**
     * 垃圾方法 1000多毫秒
     */
    public static int singleNumber1(int[] nums) {
        if (nums.length>1){
            for (int xindex = 0; xindex < nums.length - 1; xindex++) {
                for (int yindex = xindex + 1; yindex < nums.length; yindex++) {
                    if (nums[xindex] > nums[yindex]) {
                        int temp = nums[xindex];
                        nums[xindex] = nums[yindex];
                        nums[yindex] = temp;
                    }
                }
            }
            for (int index = 1; index < nums.length - 1; index++) {
                if (!(nums[index] == nums[index - 1] || nums[index] == nums[index + 1])) {
                    return nums[index];
                }
            }
            if (nums[0]!=nums[1]){
                return nums[0];
            }
            if (nums[nums.length-1]!=nums[nums.length-2]){
                return nums[nums.length - 1];
            }
        }

        return nums[0];
    }
}
